package 链表;

import java.util.PriorityQueue;

public class No23合并K个升序链表 {

    /**
     * 给你一个链表数组，每个链表都已经按升序排列。
     *
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     *
     *  
     *
     * 示例 1：
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     * 示例 2：
     * 输入：lists = []
     * 输出：[]
     * 示例 3：
     * 输入：lists = [[]]
     * 输出：[]
     */

    public static ListNode mergeKLists(ListNode[] lists) {

        ListNode listNode=new ListNode();

        ListNode nn=listNode;

        while (true){
            ListNode node=null;
            Integer min=null;
            int index=0;
            for (int i = 0; i < lists.length; i++) {
                if(lists[i]==null){
                    //为空了表明当前元素的节点已经被遍历完了
                    continue;
                }
                if(min==null){
                    node=lists[i];
                    min=lists[i].val;
                    index=i;//当前数组的
                } else if(lists[i].val<=min){
                    //赋值并且保存最小的下标
                    node=lists[i];
                    min=lists[i].val;
                    index=i;//当前数组的
                }
            }
            if(min==null)
                break;
            //遍历出来后我们对目标元素进行变更
            lists[index]=lists[index].next;
            nn.next=node;
            nn=nn.next;
            node.next=null;//并且要断连接
        }
        return listNode.next;
    }

    private static class Node implements Comparable<Node>{

        public ListNode listNode;

        public Integer i;

        public Node(ListNode listNode, Integer i) {
            this.listNode = listNode;
            this.i = i;
        }

        @Override
        public int compareTo(Node o) {
            return this.i-o.i;
        }
    }

    /**
     * 官方优化法,使用堆,但是堆内最长存k个元素,因为k个元素就已经够了,每次取出一个,然后再吃进去取出这个的下一个(因为是升序!所以完全可以!)
     */
    public static ListNode mergeKListsGood(ListNode[] lists) {

        PriorityQueue<Node> priorityQueue=new PriorityQueue<>();
        //先每个的加入一遍
        for (ListNode listNode:lists){
            priorityQueue.add(new Node(listNode,listNode.val));
        }
        ListNode listNode=new ListNode();
        ListNode nn=listNode;

        while (!priorityQueue.isEmpty()){
            ListNode node=priorityQueue.poll().listNode;
            nn.next=node;
            nn=nn.next;
            if(node.next!=null)
                priorityQueue.add(new Node(node.next,node.next.val));
            node.next=null;
        }

        return listNode.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = ListNode.createListNode(new int[]{1, 4, 5});
        ListNode listNode2 = ListNode.createListNode(new int[]{1, 3, 4});
        ListNode listNode3 = ListNode.createListNode(new int[]{2, 6});
        ListNode[] listNodes=new ListNode[]{listNode1,listNode2,listNode3};
        ListNode result = mergeKListsGood(listNodes);
        ListNode.printListNode(result);
    }

}
